//
//  desculpa.cpp
//  complexidade
//  https://br.spoj.pl/problems/DESCULPA/
//  Created by Bruno Dias on 31/05/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.

#include <iostream>

#define MAXF 51
#define MAXT 1001

using namespace std;


/* Função que coloca o numero máximo de desculpas no cartão. Baseado no problema clássico da Mochila Booleana em PD ou Knapsack
 Pesquisei alguns pseudocodigos do problema da mochila, mas o que segui como base foi desse pdf http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf 
*/
void knapsack (int tabela_aux[MAXF][MAXT], int c, int f, int t[], int v[]) {
    for (int i = 0; i < f; i++) {
        for (int j = 0; j < c; j++) {
            if (t[i+1] > j+1) {
                tabela_aux[i+1][j+1] = tabela_aux[i][j+1];
            } else { //para achar o valor máximo de desculpas
                if ((v[i+1] + tabela_aux[i][j+1 - t[i+1]]) > tabela_aux[i][j+1]) {
                    tabela_aux[i+1][j+1] = v[i+1] + tabela_aux[i][j+1 - t[i+1]];
                } else
                    tabela_aux[i+1][j+1] = tabela_aux[i][j+1];
            }
        }
    }
    cout << tabela_aux[f][c] << "\n\n"; 
}

int main(void) {
    int tamanho, frase, test = 0; 
    int text[MAXF], value[MAXF]; 
    int tabela[MAXF][MAXT]; 
    
    while ((cin >> tamanho >> frase) && tamanho!=0 && frase!=0) {
        for (int i = 1; i <= frase; i++) {
            cin >> text[i] >> value[i];
        }
        int i;
        for(i = 0; i < tamanho;i++){
            tabela[0][i]=0;
        }
        for(i = 0; i < frase; i++){
            tabela[i][0]=0;
        }
        
        test++;
        cout << "Teste " << test << "\n";
        knapsack(tabela, tamanho, frase, text, value);
    }
}
